package me.shan.sort.heap;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 * 最大重合线段数量问题
 * <p>1.两个数表示一个线段，[n,m]表示线段从n到m，其中n<m</p>
 * <p>2.如果两个线段中有多个点重合，则说明线段重合，比如：[1,3]和[2,4]，在[2,3]重合，此时重合的线段数量为1</p>
 * <p>3.[1,2]和[2,3]两个线段只有一个点重合，规定为重合的线段数量为1无重复</p>
 * <p>4.给定一组线段数量数组，求其中重合线段最大的数量</p>
 * <p>
 * 示例： [1,7],[2,4],[1,3],[3,5]重合的最大线段数量为3，分别是2到3以及3到4 [1,3],[4,6]重合的最大线段数量为0
 *
 * @author liuchuang
 * @version 1.0
 * @since 2023/6/12 13:58
 */
public class RepeatLineMaxCount {

    /**
     * 比较器，统计每个线段中点出现的次数，就能知道重复的线段数的数量，比如2.5出现的次数为10，则表示线段[2,3]重复了10次
     *
     * @param array 输入数组
     * @return 结果
     */
    public int compare(int[][] array) {
        Map<Double, Integer> countMap = new HashMap<>(32);
        int max = 0;
        for (int[] line : array) {
            for (int i = line[0]; i < line[1]; i++) {
                Double key = i + 0.5;
                int value;
                if (countMap.containsKey(key)) {
                    value = countMap.get(key) + 1;
                } else {
                    value = 1;
                }
                countMap.put(key, value);
                max = Math.max(value, max);
            }
        }
        return max;
    }

    /**
     * 堆排序解决该问题 先将数组按照线段的起点排序 循环处理，将线段终点加入到小根堆，处理第k个线段数组时： a.
     * 如果小根堆根节点数大于当前线段起点数（小根堆中所有线段起点比当前线段起点小，所有终点比当前线段起点大），说明小根堆中有多少数，当前线段就有多少重复线段数 b.
     * 如果小根堆根节点数小于当前线段起点数，则将根节点弹出，并重新heapify，然后重复当前步骤
     *
     * @param array 线段数组
     * @return 结果
     */
    public int heapSolution(int[][] array) {
        // 对线段进行排序，得到根据起点递增的线段数组
        Arrays.sort(array, Comparator.comparingInt((int[] a) -> a[0]));
        int max = 0;
        int[] heap = new int[array.length];
        int heapSize = 0;
        for (int[] line : array) {
            // 将线段的最大值加入小根堆中
            heap[heapSize] = line[1];
            heapInsert(heap, heapSize++);
            // 判断当前根节点值是否小于等于线段起点，小于则弹出，否则继续进行
            while (heap[0] <= line[0]) {
                swap(heap, 0, --heapSize);
                heapify(heap, 0, heapSize);
            }
            max = Math.max(max, heapSize);
        }
        return max;
    }

    /**
     * 小根堆添加数据
     *
     * @param array 原始数组
     * @param index 添加数字的位置
     */
    private void heapInsert(int[] array, int index) {
        int fatherIndex = (index - 1) / 2;
        while (array[index] < array[fatherIndex]) {
            swap(array, index, fatherIndex);
            index = fatherIndex;
        }
    }

    /**
     * 小根堆 堆化 操作
     * @param array 待处理小根堆
     * @param index 堆化开始节点位置
     * @param heapSize 堆大小
     */
    private void heapify(int[] array, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int least = array[left + 1] < array[left] && left + 1 < heapSize ? left + 1 : left;
            least = array[least] < array[index] ? least : index;
            if (least == index) {
                break;
            }
            swap(array, least, index);
            index = least;
            left = index * 2 + 1;
        }
    }

    private void swap(int[] array, int a, int b) {
        if (array == null || a == b) {
            return;
        }
        array[a] = array[a] ^ array[b];
        array[b] = array[a] ^ array[b];
        array[a] = array[a] ^ array[b];
    }

    private int[][] generateRandomLineArray(int maxValue, int maxLen) {
        // 长度范围[1, maxLen]
        int len = (int) (Math.random() * (maxLen - 1)) + 1;
        int[][] result = new int[len][2];
        for (int i = 0; i < len; i++) {
            int max = (int) (Math.random() * maxValue);
            int min = max - ((int) (Math.random() * maxValue));
            while (max == min) {
                min = max - ((int) (Math.random() * maxValue));
            }
            result[i] = new int[]{min, max};
        }
        return result;
    }

    public static void main(String[] args) {
        RepeatLineMaxCount repeatLineMaxCount = new RepeatLineMaxCount();
        int maxValue = 1000;
        int maxLen = 10000;
        int times = 100;
        for (int i = 0; i < times; i++) {
            int[][] array = repeatLineMaxCount.generateRandomLineArray(maxValue, maxLen);
            int compare = repeatLineMaxCount.compare(array);
            int heapSolution = repeatLineMaxCount.heapSolution(array);
            if (compare != heapSolution) {
                System.out.printf("有bug：比较器结果[%d]，堆处理方式结果[%d]\n", compare, heapSolution);
                System.out.println("数据样本：" + Arrays.deepToString(array));
                break;
            }
        }
    }
}
